package algorithm.sorting.compare.quicksort;

import java.util.Random;
import algorithm.sorting.ISort;
import algorithm.sorting.compare.insertsort.InsertSorter;
/**
 * @author lancyguy
 * @author cgzh@hotmail.com
 * @param <T> type of the elements to be sorted
 */
public class QuickSorter<T extends Comparable<T>> implements ISort<T>{
    /**
     * no secondary sorter used by default
     */
    public QuickSorter(){
		recursionThreshold = 1;
		secondSorter = null;//set to null cause never used 
	}
    /**
     * if no secondary sorter assigned, then use insert sorter
     * @see algorithm.sorting.compare.insertsort.InsertSorter
     * @param rt recursion threshold
     */
	public QuickSorter(int rt){
		recursionThreshold = rt;
		secondSorter = new InsertSorter<T>();
	}
    /**
     * @param rt recursion threshold
     * @param sorter secondary sorter
     */
	public QuickSorter(int rt, ISort<T> sorter){
		recursionThreshold = rt;
		secondSorter = sorter;
	}
    /**
     * sort the whole array
     * @param arr array to be sorted
     */
	public void sort(T[] arr) {
		sort(arr,0,arr.length-1);
	}
    /**
     * @param arr array to be sorted
     * @param head left boundary of the range of the array within which the sorting takes place
     * @param end  right boundary of the range of the array within which the sorting takes place.
     */
	public void sort(T[] arr, int head, int end) {
		if(arr.length==0 || head<0 || end>=arr.length || end-head<=0) 
    		return;
		if(end-head+1<this.recursionThreshold){
			secondSorter.sort(arr,head,end);
			return;
		}
		int pivot = doubleDirectionSplit(arr,head,end);
		sort(arr,head,pivot-1);
		sort(arr,pivot+1,end);
	}
	private int doubleDirectionSplit(T[] arr,int head,int end){
		int len = end-head+1;
		swap(arr, head, head+random.nextInt(len));
		int h = head+1;
		int e = end;
        T headValue = arr[head];
		while(h <= e){
			while(h<=end && arr[h].compareTo(headValue)<=0)
				h++;
			while(e>head && arr[e].compareTo(headValue)>=0)
				e--;
			if(h<e){
				swap(arr, h, e);
			}
		}
		swap(arr, head, e);
		return e;
	}
    private int singleDirectionSplit(T[] arr,int head,int end){
        int len = end-head+1;
		swap(arr, head, head+random.nextInt(len));
		int h = head+1;
		int e = end;
		while(h <= e){
			while(h<=end && arr[h].compareTo(arr[head])<=0)
				h++;
			while(e>head && arr[e].compareTo(arr[head])>=0)
				e--;
			if(h<e){
				swap(arr, h, e);
			}
		}
		swap(arr, head, e);
		return e;
    }

	private void swap(T[] arr,int i,int j){
		T temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	private static Random random = new Random();
	private int recursionThreshold;  //if the size of the range below this value, use secondary Sorter to optimize the sorting.
	private ISort<T> secondSorter;   // secondary sorter
}
